package com.hy;

import java.util.HashMap;
import java.util.Map;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * <p>
 * User:Mr.Du
 * Date:2024/3/29
 * Time:16:26
 */
public class TotalFruit {

    /**
     * 计算连续水果最长长度
     *
     * @param fruits 包含不同类型水果的整数数组
     * @return 连续水果种类不超过2种的最长长度
     */
    public int totalFruit1(int[] fruits) {
        int n = fruits.length; // 数组长度
        int l = 0, r = 0, res = 0, cnt = 0; // l左指针，r右指针，res最长长度，cnt当前水果种类数
        int[] nums = new int[100000]; // 数组用于计数各个水果出现的次数
        // 遍历数组
        while(r < n){
            int x = fruits[r]; // 当前水果类型
            if(nums[x] == 0) cnt++; // 如果当前水果类型第一次出现，则种类数加1
            nums[x]++; // 当前水果类型计数加1
            // 当前水果种类数超过2种时，移动左指针，直到种类数不超过2
            while(cnt > 2){
                cnt--;
                int t = r - 1;
                // 查找左指针位置，使得当前区间水果种类不超过2种
                while(t > 0){
                    if(fruits[t] == fruits[t-1]) t--;
                    else{
                        nums[fruits[t-1]] = 0; // 移除左指针之前的水果类型计数
                        break;
                    }
                }
                l = t; // 更新左指针位置
                nums[fruits[l]] = 1; // 更新左指针位置的水果类型计数为1
            }
            r++; // 右指针右移
            res = Math.max(res, r - l); // 更新最长长度
        }
        return res; // 返回最长长度
    }

    /**
     * 计算水果最长连续段的长度
     *
     * @param fruits 包含不同类型的水果的整数数组
     * @return 返回数组中包含不超过两种水果的最长连续段的长度
     */
    public int totalFruit(int[] fruits) {
        int n = fruits.length; // 数组的长度
        int l = 0, r = 0, res = 0; // 左指针l、右指针r和结果res的初始化
        Map<Integer, Integer> fruitCounts = new HashMap<>(); // 用于存储水果计数的映射

        // 遍历数组
        while (r < n) {
            // 更新右指针所指水果的计数
            fruitCounts.put(fruits[r], fruitCounts.getOrDefault(fruits[r], 0) + 1);

            // 当水果种类超过两种时，移动左指针，直到水果种类不超过两种
            while (fruitCounts.size() > 2) {
                fruitCounts.put(fruits[l], fruitCounts.get(fruits[l]) - 1);
                // 如果某种水果计数变为0，则从映射中移除该水果
                if (fruitCounts.get(fruits[l]) == 0) {
                    fruitCounts.remove(fruits[l]);
                }
                l++;
            }
            // 更新结果为当前窗口大小（右指针位置 - 左指针位置 + 1）与之前结果的最大值
            res = Math.max(res, r - l + 1);
            r++; // 右指针右移
        }
        return res; // 返回最长连续段的长度
    }
}
